/*-------------------------------------------------------------------------
 *
 * tuplesort.h
 *	  通用元组排序例程。
 *
 * 本模块处理堆元组、索引元组或单个 Datums 的排序
 * （并且可以轻松支持其他类型的可排序对象，如果需要的话）。
 * 它对少量和大量数据都能高效工作。少量数据使用 qsort() 在内存
 * 中排序。大量数据使用临时文件和标准外部排序算法进行排序。
 * 并行排序使用这种外部排序算法的变种，通常只用于大量数据。
 *
 * Portions Copyright (c) 1996-2022, PostgreSQL Global Development Group
 * Portions Copyright (c) 1994, Regents of the University of California
 *
 * src/include/utils/tuplesort.h
 *
 *-------------------------------------------------------------------------
 */
#ifndef TUPLESORT_H
#define TUPLESORT_H

#include "access/itup.h"
#include "executor/tuptable.h"
#include "storage/dsm.h"
#include "utils/relcache.h"


/*
 * Tuplesortstate和Sharedsort是opaque类型，其细节在tuplesort.c之外不可知。
 */
typedef struct Tuplesortstate Tuplesortstate;
typedef struct Sharedsort Sharedsort;

/*
 * Tuplesort并行协调状态，由每个参与者在本地内存中分配。参与者调用者初始化所有内容。
 * 请参见下面的使用说明。
 */
typedef struct SortCoordinateData
{
	/* 工作进程？如果不是，必须是领导者。 */
	bool		isWorker;

	/*
	 * 领导进程传递的已知启动的参与者数量（工作人员将其设置为-1）。包括领导者
	 * 参与作为工作人员所需的状态（如果有的话）。
	 */
	int			nParticipants;

	/* 私有不透明状态（指向共享内存） */
	Sharedsort *sharedsort;
}			SortCoordinateData;

typedef struct SortCoordinateData *SortCoordinate;

/*
 * 用于报告排序统计信息的数据结构。请注意，
 * TuplesortInstrumentation不能包含任何指针，因为我们
 * 有时将其放入共享内存中。
 *
 * 并行排序基础设施依赖于具有零TuplesortMethod
 * 来指示一个工作程序从未做过任何事情，因此我们将零分配给
 * SORT_TYPE_STILL_IN_PROGRESS。该枚举的其他值可以
 * 使用按位或组合在一起，以表示不同工作程序使用
 * 不同方法的情况，因此我们需要为每个方法保留一个单独的位。保持
 * NUM_TUPLESORTMETHODS常数与位数保持同步！
 */
typedef enum
{
	SORT_TYPE_STILL_IN_PROGRESS = 0,
	SORT_TYPE_TOP_N_HEAPSORT = 1 << 0,
	SORT_TYPE_QUICKSORT = 1 << 1,
	SORT_TYPE_EXTERNAL_SORT = 1 << 2,
	SORT_TYPE_EXTERNAL_MERGE = 1 << 3
} TuplesortMethod;

#define NUM_TUPLESORTMETHODS 4

typedef enum
{
	SORT_SPACE_TYPE_DISK,
	SORT_SPACE_TYPE_MEMORY
} TuplesortSpaceType;

/* 元组排序的按位选项标志 */
#define TUPLESORT_NONE					0

/* 指定是否需要对排序结果进行非顺序访问 */
#define	TUPLESORT_RANDOMACCESS			(1 << 0)

/* 指定元组排序是否能够支持有界排序 */
#define TUPLESORT_ALLOWBOUNDED			(1 << 1)

typedef struct TuplesortInstrumentation
{
	TuplesortMethod sortMethod; /* 使用的排序算法 */
	TuplesortSpaceType spaceType;	/* spaceUsed 表示的空间类型 */
	int64		spaceUsed;		/* 空间消耗，单位为 kB */
} TuplesortInstrumentation;



/*
 * 我们提供多个接口来处理本质上相同的代码，
 * 因为不同的调用者有不同的数据需要排序，并希望
 * 以不同的方式指定排序关键字信息。对
 * HeapTuples有两个API，对
 * IndexTuples还有两个API。另一个API支持排序裸
 * Datums。
 *
 * 串行排序调用者应为其坐标参数传递NULL。
 *
 * “heap” API实际上存储/排序的是MinimalTuples，这意味着它不
 * 保留系统列（元组身份和事务可见性
 * 信息）。排序关键字通过元组中的列号
 * 和排序运算符OID指定。我们通过在TupleTableSlots中传递和返回
 * 元组来节省一些周期，而不是形成实际的HeapTuples（这需要
 * 转换为MinimalTuples）。该API适用于作为计划树部分执行的排序。
 *
 * “cluster” API存储/排序完整的HeapTuples，包括所有可见性
 * 信息。排序关键字通过引用在要排序的关系上定义的btree索引
 * 来指定。请注意，putheaptuple/getheaptuple与此API配合使用，而不是
 * “begin_heap” API！
 *
 * “index_btree” API存储/排序IndexTuples（保留所有它们的
 * 头部字段）。排序关键字通过btree索引定义来指定。
 *
 * “index_hash” API类似于index_btree，但元组实际上是通过
 * 它们的哈希码而不是原始数据来排序的。
 *
 * 并行排序调用者要求在领导进程和一个或多个工作进程中协调多个
 * tuplesort状态。领导进程必须启动工作进程，并让每个工作进程
 * 执行独立的“部分”tuplesort，通常由并行堆接口提供数据。最后，
 * 领导者生成最终输出（内部，它合并工作进程的输出结果）。
 *
 * 调用者必须执行以下操作，以便使用多个
 * 工作进程进行并行排序：
 *
 * 1. 为n个工作进程请求tuplesort私有的共享内存。使用
 *    tuplesort_estimate_shared()获取所需的大小。
 * 2. 让领导进程使用tuplesort_initialize_shared()初始化分配的
 *    共享内存。启动工作进程。
 * 3. 在领导进程和每个工作进程内初始化一个坐标参数。该参数有一个
 *    指向共享
 *    tuplesort私有结构的指针，以及一些调用者初始化的字段。
 *    领导者的坐标参数可靠地指示已启动的工作进程数
 *    （这在工作进程中未使用）。
 * 4. 在每个工作进程中使用某个适当的tuplesort_begin*例程启动
 *    tuplesort（传递坐标参数）。workMem
 *    参数不必完全相同。所有其他参数应完全匹配。
 * 5. 所有工作进程都应调用tuplesort_attach_shared()。给每个工作进程
 *    提供元组，在输入耗尽时调用每个工作进程中的tuplesort_performsort()。
 * 6. 在每个工作进程中调用tuplesort_end()。工作进程可以在
 *    tuplesort_end()返回后关闭。
 * 7. 使用相同的tuplesort_begin*例程在领导者中开始tuplesort，
 *    传递适合领导者的坐标参数（实际上，这可以尽早在步骤3中发生，
 *    因为我们只需知道成功启动的工作进程数量）。领导者现在必须等待
 *    工作进程完成。调用者必须使用自己的机制确保在所有工作进程
 *    调用并返回tuplesort_performsort()之前，不会进入下一步。
 *    （注意，工作进程已经调用tuplesort_end()是可以的。）
 * 8. 在领导进程中调用tuplesort_performsort()。使用适当的
 *    tuplesort_get*例程消耗输出。如果tuplesort被证明是不必要的，
 *    领导者可以跳过此步骤。
 * 9. 在领导者中调用tuplesort_end()。
 *
 * 这种劳动分工不假设输入元组的生成方式，
 * 但确实要求调用者结合多个tuplesorts的状态，以满足
 * 其他目的，而不仅仅是生成最终输出。例如，调用者
 * 必须考虑tuplesort_get_stats()仅报告一个工作进程在
 * 排序中的角色（或领导者的角色），而不是整个排序的统计数据。
 *
 * 请注意，调用者可以使用领导进程对运行进行排序，就像它是一个
 * 独立的工作进程一样（在该进程执行领导排序以生成最终排序
 * 输出之前）。这样做仅需要在领导进程内进行第二个
 * “部分”tuplesort，初始化方式与工作进程相同。上述步骤没有直接触及这一点。
 * 唯一的区别是，领导进程中从不需要tuplesort_attach_shared()
 * 调用，因为后端整体持有共享文件集的引用。领导者中的工作
 * Tuplesortstate预期与工作进程的Tuplesortstate执行相同数量的
 * 初始处理工作，因为领导进程在工作进程完成之前没有其他事情可做。
 *
 * 请注意，仅在领导状态第一次消耗输入之前，将分配非常少量的内存，
 * 并且工作进程在从tuplesort_performsort()返回时将释放
 * 绝大部分内存。调用者可以依赖此安排，以使内存的使用尊重
 * 整个并行排序操作的workMem风格预算。
 *
 * 调用者一般负责并行安全。然而，他们
 * 至少可以依靠tuplesort内部不存在并行安全隐患，
 * 因为tuplesort将排序视为几个独立排序的组合，结果被合并。
 * 因为一般来说，排序运算符的行为是不可变的，调用者只需
 * 担心生成输入元组的进程的并行安全（通常，调用者使用并行
 * 堆扫描）。
 */ 

extern Tuplesortstate *tuplesort_begin_heap(TupleDesc tupDesc,
											int nkeys, AttrNumber *attNums,
											Oid *sortOperators, Oid *sortCollations,
											bool *nullsFirstFlags,
											int workMem, SortCoordinate coordinate,
											int sortopt);
extern Tuplesortstate *tuplesort_begin_cluster(TupleDesc tupDesc,
											   Relation indexRel, int workMem,
											   SortCoordinate coordinate,
											   int sortopt);
extern Tuplesortstate *tuplesort_begin_index_btree(Relation heapRel,
												   Relation indexRel,
												   bool enforceUnique,
												   bool uniqueNullsNotDistinct,
												   int workMem, SortCoordinate coordinate,
												   int sortopt);
extern Tuplesortstate *tuplesort_begin_index_hash(Relation heapRel,
												  Relation indexRel,
												  uint32 high_mask,
												  uint32 low_mask,
												  uint32 max_buckets,
												  int workMem, SortCoordinate coordinate,
												  int sortopt);
extern Tuplesortstate *tuplesort_begin_index_gist(Relation heapRel,
												  Relation indexRel,
												  int workMem, SortCoordinate coordinate,
												  int sortopt);
extern Tuplesortstate *tuplesort_begin_datum(Oid datumType,
											 Oid sortOperator, Oid sortCollation,
											 bool nullsFirstFlag,
											 int workMem, SortCoordinate coordinate,
											 int sortopt);

extern void tuplesort_set_bound(Tuplesortstate *state, int64 bound);
extern bool tuplesort_used_bound(Tuplesortstate *state);

extern void tuplesort_puttupleslot(Tuplesortstate *state,
								   TupleTableSlot *slot);
extern void tuplesort_putheaptuple(Tuplesortstate *state, HeapTuple tup);
extern void tuplesort_putindextuplevalues(Tuplesortstate *state,
										  Relation rel, ItemPointer self,
										  Datum *values, bool *isnull);
extern void tuplesort_putdatum(Tuplesortstate *state, Datum val,
							   bool isNull);

extern void tuplesort_performsort(Tuplesortstate *state);

extern bool tuplesort_gettupleslot(Tuplesortstate *state, bool forward,
								   bool copy, TupleTableSlot *slot, Datum *abbrev);
extern HeapTuple tuplesort_getheaptuple(Tuplesortstate *state, bool forward);
extern IndexTuple tuplesort_getindextuple(Tuplesortstate *state, bool forward);
extern bool tuplesort_getdatum(Tuplesortstate *state, bool forward,
							   Datum *val, bool *isNull, Datum *abbrev);

extern bool tuplesort_skiptuples(Tuplesortstate *state, int64 ntuples,
								 bool forward);

extern void tuplesort_end(Tuplesortstate *state);

extern void tuplesort_reset(Tuplesortstate *state);

extern void tuplesort_get_stats(Tuplesortstate *state,
								TuplesortInstrumentation *stats);
extern const char *tuplesort_method_name(TuplesortMethod m);
extern const char *tuplesort_space_type_name(TuplesortSpaceType t);

extern int	tuplesort_merge_order(int64 allowedMem);

extern Size tuplesort_estimate_shared(int nworkers);
extern void tuplesort_initialize_shared(Sharedsort *shared, int nWorkers,
										dsm_segment *seg);
extern void tuplesort_attach_shared(Sharedsort *shared, dsm_segment *seg);


/*
 * 这些例程只能在 tuplesort_begin_* 时指定了 TUPLESORT_RANDOMACCESS 的情况下调用。
 * 此外，在 gettuple/getdatum 中的反向扫描也需要 TUPLESORT_RANDOMACCESS。
 * 请注意，并行排序不支持随机访问。
 */
extern void tuplesort_rescan(Tuplesortstate *state);
extern void tuplesort_markpos(Tuplesortstate *state);
extern void tuplesort_restorepos(Tuplesortstate *state);

#endif							/* TUPLESORT_H */
